package exercises.leetcode;

import java.util.ArrayDeque;

/**
 * <a href="https://leetcode-cn.com/problems/132-pattern/">
 * 456. 132 模式</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 * <p>
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3,4]
 * 输出：false
 * 解释：序列中不存在 132 模式的子序列。
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [3,1,4,2]
 * 输出：true
 * 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
 * <p>
 * 示例 3：
 * <p>
 * 输入：nums = [-1,3,2,0]
 * 输出：true
 * 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
 *  
 * <p>
 * 提示：
 * <li>n == nums.length</li>
 * <li>1 <= n <= 2 * 105</li>
 * <li>-109 <= nums[i] <= 109</li>
 *
 * @author or2
 * @date 2021年10月04日 时间: 16:21
 */
public class No456 {
    public boolean find132pattern(int[] nums) {
        var stack = new ArrayDeque<Integer>();
        stack.push(nums[nums.length - 1]);
        for (int index = nums.length - 2, secondary = (int) (-1e9-1); index >= 0; index--) {
            if (nums[index] < secondary)
                return true;
            while (!stack.isEmpty() && nums[index] > stack.peek())
                secondary = stack.poll();
            stack.push(nums[index]);
        }
        new StringBuilder();
        return false;
    }
}
